package day1.linkedlist;

/**
 * @author pacai
 * @version 1.0
 * 有序链表合并
 */

@SuppressWarnings("all")
public class MergeTwoSortedLink {
    static class Node{
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public static Node mergeTwoSortedLinks(Node head1, Node head2) {
        //边界条件
        if(head1==null || head2==null){
            return head1 == null ? head2 : head1;
        }
        Node head = head1.data < head2.data ? head1 : head2;
        Node cur1 = head.next;
        Node cur2 = head == head1 ? head2 : head1;
        Node pre = head;

        while(cur1 != null && cur2 != null){
            if(cur1.data <= cur2.data){
                pre.next = cur1;
                cur1 =cur1.next;
            }else{
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }
}
